#pragma once
#include <vector>

class UnionFindSet
{
public:
	UnionFindSet(int size)
		: _set(size, -1)
	{}

	size_t FindRoot(int x)
	{
		while(_set[x] >= 0)
			x = _set[x];

		return x;
	}

	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		if(root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;
		}
	}

	size_t SetCount()
	{
		size_t count = 0;
		for(size_t i = 0; i < _set.size(); ++i)
		{
			if(_set[i] < 0)
				count++;
		}

		return count;
	}

private:
	std::vector<int> _set;
};

void TestUFS()
{
	UnionFindSet u(10);

	u.Union(0, 6);
	u.Union(7, 6);
	u.Union(7, 8);

	u.Union(1, 4);
	u.Union(4, 9);

	u.Union(2, 3);
	u.Union(2, 5);

	cout<<u.SetCount()<<endl;
}
